package leetcode;

public class Code727 {
    public static void main(String[] args) {
        int[] start=new int[]{2, 3, 5, 7, 11, 13, 17, 19, 23};
        int[] end   =new int[start.length];
        for (int a=0;a<end.length;a++){
            end[a]=((int)(Math.random()*(start[a]-1))==0)?1:((int)(Math.random()*(start[a]-1)));
        }
        for (int a=0;a<start.length;a++){
            System.out.println(start[a]+":"+end[a]);
        }
        new Code727().isOk(start,end,new Code727().remainderTheorem(start,end));
        new Code727().isOk(start,end,new Code727().remainderTheorem2(start,end));
    }

    private void isOk(int[] start, int[] end, int i) {
        System.out.println("答案："+i);
        System.out.println("验证:");
        for (int a=0;a<start.length;a++){
            if (i%start[a]!=end[a]){
                System.out.println("错误");
                return;
            }
        }
        System.out.println("正确");
    }

    /**
     * int temp = num[0];
     * //ret指的是到下标为X时的结果，初始化为下标为0时的数据
     * int ret = rem[0];
     * for (int i = 1; i < num.length; i++) {
     * for (int j = 0;; j++) {
     * //找到满足条件的最小整数
     * if ((ret + n * j) % num[i] == rem[i]) {
     * ret = ret + n * j;
     * temp *= num[i];
     * break;
     * }
     * }
     * }
     *
     * @param num
     * @param rem
     * @return
     */

    public int remainderTheorem(int[] num, int[] rem) {
        int r = rem[0];
        int n = num[0];
        for (int a = 1; a < num.length; a++) {
            for (int b = 0; ; b++) {
                if ((n * b + r) % num[a] == rem[a]) {
                    r = n * b + r;
                    n = n * num[a];
                    break;
                }
            }

        }
        return r;
    }


    /**
     * 高级写法
     *
     * @param num
     * @param rem
     * @return
     */
    public int remainderTheorem2(int[] num, int[] rem) {
        // write your code here
        if (num.length == 0 || rem.length == 0)
            return 0;
        int len = num.length;
        int n = num[0];
        int r = rem[0];
        for (int i = 1; i < len; ++i) {
            int a = (rem[i] - r % num[i] + num[i]) % num[i];
            if (a != 0) {
                for (int j = 1; j <= num[i]; ++j) {
                    if (n * j % num[i] == a) {
                        r = n * j + r;
                        break;
                    }
                }
            }
            n = num[i] * n;
        }
        return r;
    }
}
